package algorithm.lanqiao.t109;

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

public class Main {
    static class IO {
        // 读
        static InputStreamReader ins = new InputStreamReader(System.in);
        static StreamTokenizer in = new StreamTokenizer(ins);
        static BufferedReader br = new BufferedReader(ins);

        // 写
        public static PrintWriter out = new PrintWriter(System.out);


        public static int readInt() {
            try {
                in.nextToken();
            } catch (Exception e) {
                e.printStackTrace();
            }
            return (int) in.nval;
        }

        public static String readLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
    final static int N = 150;
    final static int[][] g = new int[N][N];
    final static int[][] classes = new int[N][N];
    static int ans = N;
    static int n;
    static int m;

    public static void main(String[] args) {
         n = IO.readInt();
        m = IO.readInt();
        for(int i = 0; i < m; i++) {
            int a = IO.readInt(), b = IO.readInt();
            g[a][b] = 1;
            g[b][a] = 1;
        }
        dfs(1,1);
        IO.out.println(ans);
        IO.out.flush();
    }

    private static void dfs(int x, int classNumber) {
        if(classNumber >= ans) {
            return;
        }
        if(x > n){
            ans = classNumber;
            return;
        }
        for(int i = 1; i <= classNumber; i++) {
            int k = 1;
            while(classes[i][k] != 0 && g[x][classes[i][k]] != 1) {
                k ++;
            }
            if(classes[i][k] == 0) {
                classes[i][k] = x;
                dfs(x+1, classNumber);
                classes[i][k] = 0;
            }
        }
        classes[classNumber+1][1] = x;
        dfs(x+1, classNumber+1);
        classes[classNumber+1][1] = 0;
    }


}
